{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 凸集与凸函数\n",
    "\n",
    "* **凸集**: $n$维欧氏空间中的点集,如果点集中的任意两点的连线都包含在这个点集,则这个点集是凸集.\n",
    "* **凸集分离定理**: 两个不相交的非空凸集,一定可以用一个超平面分离这两个凸集.\n",
    "* **凸函数(convex function)**:对于函数$f$定义域内的任意两点$x,y$,如果有$$f(\\theta x+(1-\\theta y))\\leq \\theta f(x)+(1-\\theta)f(y)$$则称$f$为凸函数.如果$-f$为凸函数,则称$f$为凹函数(concave function)\n",
    "* 一个函数的epigraph定义为:$$epi f:=\\{(x,z):x \\in dom f,z\\geq f(x)\\}$$\n",
    "* 函数$f(x)$为凸函数当且仅当$epi f$为凸集.\n",
    "* **严格凸函数** :凸函数定义中的不等号为严格不等号.\n",
    "* **强凸函数** :存在$m>0$使得$f(x)-\\frac{m}{2}||x||^2$为凸函数,其中的$m$称为函数$f$的强凸系数.\n",
    "* 如果函数$f$可导,且对于定义域内的所有$x,y$都有$$f(y)\\geq f(x)+\\triangledown f(x)^T(y-x)$$则$f$为凸函数.更进一步,如果存在正数$m$使得$$f(y)\\geq f(x)+\\triangledown f(x)^T(y-x)+\\frac{m}{2}||x-y||^2$$则$f$为系数为$m$的强凸函数.\n",
    "* **凸函数的Hessian矩阵** :对于一个多元函数$f(x_1,x_2,...,x_n)$,定义其Hessian矩阵为$$\\triangledown ^2 f:=(D_{ij})_{1\\leq i,j\\leq d} , D_{ij}=\\frac{\\partial ^2f}{\\partial x_i\\partial x_j}$$梯度算子是一元函数的导数在多元函数的推广,Hessian矩阵是一元函数的二阶导在多元函数的推广.\n",
    "* 如果函数$f$二阶可导,且其Hessian矩阵半正定,则$f$是凸函数.\n",
    "* 如果函数$f$二阶可导,且$\\triangledown ^2 f-mI$半正定(m>0),则$f$是系数为m的强凸函数.\n",
    "凸函数的一些性质:\n",
    "* 凸函数的局部最小值是全局最小值.    \n",
    "* $x_0$为可导的凸函数$f$的全局最小值$\\Longleftrightarrow \\triangledown f(x_0)=0$.\n",
    "* 琴生不等式及推广:\n",
    "$$f(\\theta x+(1-\\theta y))\\leq \\theta f(x)+(1-\\theta)f(y)$$\n",
    "$$f(\\sum_{i=1}^k \\theta_iX_i))\\leq \\sum_{i=1}^k\\theta_i f(x_i),\\sum_{i=1}^k \\theta_i=1$$\n",
    "$$f(\\int_{S} p(x)xdx)\\leq \\int_S f(x)p(x)dx,\\int_{S} p(x)dx=1$$\n",
    "$$f(\\mathbb{E}[x])\\leq \\mathbb{E}[f(x)]$$\n",
    "* 多个凸函数的非负线性组合还是凸函数.凸函数的逐点最大化还是凸函数.凸函数的最小化($g(x)=inf_{y\\in \\mathcal{C}}f(x,y),\\mathcal{C}$是非空凸集)还是凸函数."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 最优化问题\n",
    "* 定义:最优化问题是指在一定约束条件下,求解一个目标函数的最小值(或最大值)的问题.其数学形式为$$\\min_{x\\in \\mathcal{C}} f(x)   $$称$f$为目标函数,$x$为决策变量,$\\mathcal{C}$为可行域.如果可行域为整个空间,则称这个问题为无约束优化问题.\n",
    "* **线性规划(Linear programming)** 研究线性约束条件下线性目标函数的极致问题,常用解法有单纯型法等.如果目标函数为二次函数,则称为**二次规划(Quadratic Programming)** 问题.机器学习中的许多优化问题都属于二次规划,例如,最小二乘回归,支持向量机等.如果一个最优化问题的目标函数是凸函数,且可行域是凸集,则称这样的问题为**凸优化问题** ,线性规划和二次规划都是凸优化问题.\n",
    "* 极值点的$\\varepsilon -\\delta$定义\n",
    "* 极值点是局部最优的,不一定是全局最优的,但凸函数的极小值点也是最小值点.\n",
    "## 无约束问题的最优性条件\n",
    "* 一阶必要条件: 在极值点$x_0$可微的函数$f(x)$,满足$\\triangledown f(x_0)=0$,(如果是一元函数,就是在该点的导数等于零).\n",
    " * 二阶必要条件: 在极值点$x_0$二次可微的函数$f(x)$,满足$\\triangledown f(x_0)=0,$且$\\triangledown ^2f(x_0)=0$半正定.\n",
    "上述两个条件都是必要非充分条件.\n",
    "* 二阶充分条件: 在点$x_0$二次可微的函数$f(x)$,如果满足$\\triangledown f(x_0)=0,$且$\\triangledown ^2f(x_0)=0$正定,则点$x_0$是局部极小值点.\n",
    "* 一阶充要条件:$x_0$是$n$维实空间上的可微凸函数$f(x)$的极值点的充要条件是梯度$\\triangledown f(x_0)=0,$.\n",
    "* \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 梯度下降法\n",
    "\n",
    "* **函数$f(x)$在$x_t$处沿负梯度方向下降最快**\n",
    "* 梯度下降法的算法:\n",
    "选取初始点$x_0$;重复以下步骤$$x_{t+1}=x_t-\\eta _t \\triangledown f(x_t)$$,直至终止条件$||\\triangledown f(x_t)||\\leq \\varepsilon$达成.其中的$\\eta _t$在机器学习里称为学习率.\n",
    "* 选择合适的学习率(的迭代方式),使得学习率可以动态调整\n",
    "  * 精确线搜索:选取当前梯度适合的最优步长$\\eta _t= argmin_{\\eta}f(x_t-\\eta \\triangledown f(x_t))$\n",
    "  * 回溯线搜索:选择参数$\\alpha \\in (1,\\frac{1}{2}),\\beta \\in (0,1)$,令$\\eta =1,$重复$\\eta =\\beta \\eta,$直至$f(x_t-\\eta \\triangledown f(x_t))\\leq f(x_t)-\\alpha \\eta ||\\triangledown f(x_t)||^2$\n",
    "\n",
    "* 梯度下降法的收敛率\n",
    "    * Lipschitz连续性条件:$||\\triangledown f(x)-\\triangledown f(y)||_2 \\leq L||x-y||_2, L>0$\n",
    "    * 可导的凸函数$f(x)$满足$\\triangledown f(x)$是Lipschitz连续的,Lipschitz系数是$L$:\n",
    "        * 如果梯度下降法采用固定的学习率$\\eta=\\frac{1}{L}$,则$$f(x_t)-f(x^*)\\leq \\frac{||x_0-x^*||^2_2}{2t\\eta}\\sim \\frac{1}{t}$$\n",
    "        * 如果梯度下降法采用回溯线搜索来选择学习率,则$$f(x_t)-f(x^*)\\leq \\frac{||x_0-x^*||^2_2}{2tq}\\sim \\frac{1}{t},q=\\min\\{1,\\beta /L\\}$$\n",
    "    * 强凸系数为$m$的强凸函数$f(x)$满足$\\triangledown f(x)$是Lipschitz连续的,Lipschitz系数是$L$,如果梯度下降法采用固定学习率$\\eta$满足$\\eta \\leq \\frac{2}{m+L},$或者采用回溯线搜索来选择学习率,那么有$$f(x_t)-f(x^*)\\leq \\frac{c^tL||x_0-x^*||^1_2}{2}\\sim c^t,c \\in (0,1)$$\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 牛顿法\n",
    "\n",
    "* 算法思想:  \n",
    "对目标函数$f(x_t+\\Delta x)$在$x_t$处进行二阶泰勒展开,得到关于$\\Delta x$的二次函数\n",
    "$$f(x_t+\\Delta x)\\approx f(x_t)+\\triangledown f(x_t)^T\\Delta x +\\frac{1}{2}\\Delta x^T\\triangledown f(x_t)\\Delta x$$\n",
    "取最小值时,$$\\Delta x=-[\\triangledown f(x_t)]^{-1}\\triangledown f(x_t)$$\n",
    "牛顿法的迭代公式为 $$x_{t+1}=x_t-[\\triangledown ^2f(x_t)]^{-1}\\triangledown f(x_t)$$\n",
    "* 收敛率:  \n",
    "强凸系数为$m$的凸函数$f(x)$如果$\\triangledown ^2f(x)$是Lipschitz连续的,Lipschitz系数为$L$,那么存在一个常数$\\lambda \\in(0,m^2/L)$使得当初始点$x_0$满足$||\\triangledown f(x_0)||\\leq \\lambda$时,有$$\\frac{L}{2m^2}||\\triangledown f(x_t)||\\leq (\\frac{L}{2m^2}||\\triangledown f(x_0)||^{2^t}\\leq (\\frac{1}{2}))^{2^t}$$特别地, 对于二次凸函数, 用牛顿法经历一次迭代即达极小点. \n",
    "## 阻尼牛顿法:\n",
    "* 值得注意, 当初始点远离极小点时, 牛顿法可能不收敛, 因为牛顿方向不一定是下降方向, 经迭代, 目标函数值可能上升. 针对这一问题进行修正, 人们提出了 阻尼牛顿法.\n",
    "* 为了保证每次迭代都能使得目标函数下降,阻尼牛顿法在牛顿法的基础上增加了沿着牛顿方向的步长搜索,迭代公式为$$x_{t+1}=x_t+\\eta _t\\Delta x_t$$,其中$\\Delta x_t=-[\\triangledown ^2f(x_t)]^{-1}\\triangledown f(x_t)$为牛顿方向.$\\eta _t$的选取可以次啊用精确线搜索或者回溯线搜索.\n",
    "* 当目标函数是强凸函数,且$\\triangledown ^2f(x)$是Lipschitz连续时,阻尼牛顿法具有全局收敛性.\n",
    "## 拟牛顿法\n",
    "* 牛顿法需要计算二阶偏导, 而且目标函数的Hesse矩阵可能非正定. 为克服这些问题, 人们提出了拟牛 顿法, 基本思想是用不含二阶导数的矩阵A来近似原Hesse矩阵的逆矩阵H−1. 根据得到近似矩阵A的方法的不同, 拟牛顿法也有不同的变体."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 带约束优化问题 \n",
    "见https://www.boyuai.com/elites/course/D91JM0bv72Zop1D3/lesson/XzjgAxtIBJpa83rRIkH7J5\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 凸优化\n",
    "* 极小值点:局部最小值点.\n",
    "* 鞍点:一阶导和二阶导在该点都等于零.\n",
    "* 梯度消失:在神经网络中，当前面隐藏层的学习速率低于后面隐藏层的学习速率，即随着隐藏层数目的增加，分类准确率反而下降了。这种现象叫做消失的梯度问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
